// 《围棋》作者版权所有。版权所有。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package ssa

import (
	"fmt"
	"os"
)

// 如果为真，请在每次突变后检查偏序集的完整性
var debugPoset = false

const uintSize = 32 << (^uint(0) >> 63) // 32或64 

// 位集是密集索引的位数组。
type bitset []uint

func newBitset(n int) bitset {
	return make(bitset, (n+uintSize-1)/uintSize)
}

func (bs bitset) Reset() {
	for i := range bs {
		bs[i] = 0
	}
}

func (bs bitset) Set(idx uint32) {
	bs[idx/uintSize] |= 1 << (idx % uintSize)
}

func (bs bitset) Clear(idx uint32) {
	bs[idx/uintSize] &^= 1 << (idx % uintSize)
}

func (bs bitset) Test(idx uint32) bool {
	return bs[idx/uintSize]&(1<<(idx%uintSize)) != 0
}

type undoType uint8

const (
	undoInvalid     undoType = iota
	undoCheckpoint           // 组撤消的检查点通过
	undoSetChl               // 更改为撤消的左子级。idx来撤销。edge 
	undoSetChr               // 更改回undo的右子级。idx来撤销。边缘
	undoNonEqual             // 忘记SSA值撤消。ID不等于undo。idx（另一个ID）
	undoNewNode              // 删除为SSA值撤消创建的新节点。ID 
	undoNewConstant          // 从常量映射中删除常量节点idx 
	undoAliasNode            // unalias SSA值撤消。ID，使其指向节点索引撤消。idx 
	undoNewRoot              // 删除节点撤消。根列表中的idx 
	undoChangeRoot           // 删除节点撤消。从根列表中删除idx，然后放回撤消。边改为目标
	undoMergeRoot            // 删除节点撤消。从根列表中删除idx，并将其子项放回
)

// posetUndo表示要执行的撤消过程。
// 它是可用于存储信息的字段的并集，
// 而typ是判别式，指定必须执行哪种类型的
// 操作。并非所有字段都始终使用。
type posetUndo struct {
	typ  undoType
	idx  uint32
	ID   ID
	edge posetEdge
}

const (
	// 使偏序集将常量作为无符号数处理。
	posetFlagUnsigned = 1 << iota
)

// 偏序集边。零值是空/空边。
// 打包目标节点索引（31位）和严格标志（1位）。
type posetEdge uint32

func newedge(t uint32, strict bool) posetEdge {
	s := uint32(0)
	if strict {
		s = 1
	}
	return posetEdge(t<<1 | s)
}
func (e posetEdge) Target() uint32 { return uint32(e) >> 1 }
func (e posetEdge) Strict() bool   { return uint32(e)&1 != 0 }
func (e posetEdge) String() string {
	s := fmt.Sprint(e.Target())
	if e.Strict() {
		s += "*"
	}
	return s
}

// posetNode是偏序集中DAG的一个节点。
type posetNode struct {
	l, r posetEdge
}

// 偏序集是一种联合查找数据结构，可以表示SSA值的偏序集
// 。给定一个创建偏序的二进制关系（例如：“<”），
// 客户端可以使用SetOrder记录SSA值之间的关系，然后
// 使用Ordered检查关系（在传递闭包中）。例如，如果调用SetOrder来记录A<B和B<C，Ordered将在稍后确认A<C.
// 
// 可以用SetEqual记录SSA值之间的相等关系，并用Equal检查
// 相等。等式传播到部分
// 顺序的传递闭包中，因此，如果我们知道A<B<C，然后了解到A==D，Ordered将返回
// 对于D<C.
// 
// 也可以用SetNonEqual记录节点之间的不等式关系；
// 非平等关系不是可传递的，但它们仍然有用：例如
// 如果我们知道A<=B，后来我们知道A=B、 我们可以推断A<B.
// NonEqual可用于检查是否已知节点不同，要么是因为之前调用过SetNonEqual，要么是因为我们知道它们是严格排序的。
// 
// poset将拒绝记录与现有关系相矛盾的新关系：
// 例如，如果A<B<C，调用C<A的SetOrder将无法返回false；另外，调用C==A的SetEqual将失败。
// 
// 偏序集被实现为DAG森林；在每个DAG中，如果从节点a到B有一条路径（定向）
// 则表示a<B（或a<=B）。相等通过将两个SSA值映射到同一个DAG节点来表示；当在两个现有节点之间记录新的相等关系
// 时，将合并节点，调整传入和传出边。
// 
// 对常数进行了特殊处理。当一个常量被添加到偏序集中时，它是
// 立即链接到其他已经存在的常量；例如，如果
// 偏序集知道x<=3，然后x与5进行测试，首先添加5并链接
// 3（使用3<5），这样偏序集知道x<=3<5；在这一点上，它能够正确地回答x<5。这意味着所有常数始终在同一个
// DAG内；作为实现细节，我们强调包含常量
// 的DAG始终是林中的第一个。
// 
// poset的设计是为了提高内存效率，并且在正常使用期间几乎不进行分配。
// 大多数内部数据结构都是预分配的、平坦的，因此，例如添加一个
// 新关系不会导致任何分配。出于性能原因，每个节点最多只有两条输出边（如二叉树），因此中间的
// “额外”节点需要表示两个以上的关系。比如
// 记录A<I，A<J，A<K（I，J，K之间没有已知的关系），我们创建了
// 以下DAG:
// 
// A 
// \
// I EXTRACT 
// \
// J K 
// 
type poset struct {
	lastidx   uint32            // 上次生成的密集索引
	flags     uint8             // 内部标志
	values    map[ID]uint32     // SSA值映射到密集索引
	constants map[int64]uint32  // 记录SSA常量及其值
	nodes     []posetNode       // 节点（在所有DAG中）
	roots     []uint32          // 根节点列表（林）
	noneq     map[uint32]bitset // 非相等关系
	undo      []posetUndo       // 撤消链
}

func newPoset() *poset {
	return &poset{
		values:    make(map[ID]uint32),
		constants: make(map[int64]uint32, 8),
		nodes:     make([]posetNode, 1, 16),
		roots:     make([]uint32, 0, 4),
		noneq:     make(map[uint32]bitset),
		undo:      make([]posetUndo, 0, 4),
	}
}

func (po *poset) SetUnsigned(uns bool) {
	if uns {
		po.flags |= posetFlagUnsigned
	} else {
		po.flags &^= posetFlagUnsigned
	}
}

// 处理子节点
func (po *poset) setchl(i uint32, l posetEdge) { po.nodes[i].l = l }
func (po *poset) setchr(i uint32, r posetEdge) { po.nodes[i].r = r }
func (po *poset) chl(i uint32) uint32          { return po.nodes[i].l.Target() }
func (po *poset) chr(i uint32) uint32          { return po.nodes[i].r.Target() }
func (po *poset) children(i uint32) (posetEdge, posetEdge) {
	return po.nodes[i].l, po.nodes[i].r
}

// upush记录一个新的撤消步骤。它可以用于简单的
// 撤销记录最多一个索引和一条边的过程。
func (po *poset) upush(typ undoType, p uint32, e posetEdge) {
	po.undo = append(po.undo, posetUndo{typ: typ, idx: p, edge: e})
}

// upushnew为一个新节点推送一个撤销过程
func (po *poset) upushnew(id ID, idx uint32) {
	po.undo = append(po.undo, posetUndo{typ: undoNewNode, ID: id, idx: idx})
}

// upushneq为一个非相等关系推送一个新撤销过程
func (po *poset) upushneq(idx1 uint32, idx2 uint32) {
	po.undo = append(po.undo, posetUndo{typ: undoNonEqual, ID: ID(idx1), idx: idx2})
}

// upushalias为两个节点别名推送一个新撤销过程
func (po *poset) upushalias(id ID, i2 uint32) {
	po.undo = append(po.undo, posetUndo{typ: undoAliasNode, ID: id, idx: i2})
}

// UPUSHCONT为一个新常数
func (po *poset) upushconst(idx uint32, old uint32) {
	po.undo = append(po.undo, posetUndo{typ: undoNewConstant, idx: idx, ID: ID(old)})
}

// addchild将i2添加为i1的直接子级。
func (po *poset) addchild(i1, i2 uint32, strict bool) {
	i1l, i1r := po.children(i1)
	e2 := newedge(i2, strict)

	if i1l == 0 {
		po.setchl(i1, e2)
		po.upush(undoSetChl, i1, 0)
	} else if i1r == 0 {
		po.setchr(i1, e2)
		po.upush(undoSetChr, i1, 0)
	} else {
		// 如果n1已经有两个子节点，则添加一个中间额外的
		// 节点以正确记录该关系（不将
		// n2与其他现有节点关联）。使用非确定性值
		// 来决定是在左边追加还是在右边追加，以避免
		// 创建退化链。
		// 
		// n1 
		// \
		// i1l额外
		// \
		// i1r n2 
		// 
		extra := po.newnode(nil)
		if (i1^i2)&1 != 0 { // 非确定性
			po.setchl(extra, i1r)
			po.setchr(extra, e2)
			po.setchr(i1, newedge(extra, false))
			po.upush(undoSetChr, i1, i1r)
		} else {
			po.setchl(extra, i1l)
			po.setchr(extra, e2)
			po.setchl(i1, newedge(extra, false))
			po.upush(undoSetChl, i1, i1l)
		}
	}
}

// newnode分配一个绑定到SSA值n的新节点。
// 如果n为零，这是一个额外的节点（=仅在内部使用）。
func (po *poset) newnode(n *Value) uint32 {
	i := po.lastidx + 1
	po.lastidx++
	po.nodes = append(po.nodes, posetNode{})
	if n != nil {
		if po.values[n.ID] != 0 {
			panic("newnode for Value already inserted")
		}
		po.values[n.ID] = i
		po.upushnew(n.ID, i)
	} else {
		po.upushnew(0, i)
	}
	return i
}

// 查找在DAG林中搜索SSA值，并返回其节点。
// 在查找过程中，常量是动态物化的。
func (po *poset) lookup(n *Value) (uint32, bool) {
	i, f := po.values[n.ID]
	if !f && n.isGenericIntConst() {
		po.newconst(n)
		i, f = po.values[n.ID]
	}
	return i, f
}

// newconst为常数创建一个节点。它将其与其他常数联系起来，因此当n<=3已知为真时，n<=5被检测为真。
// TODO:这是O（N），修复它。
func (po *poset) newconst(n *Value) {
	if !n.isGenericIntConst() {
		panic("newconst on non-constant")
	}

	// 如果相同的常量已经通过不同的
	// 值存在于偏序集中，只需为其添加别名，而无需分配新节点。
	val := n.AuxInt
	if po.flags&posetFlagUnsigned != 0 {
		val = int64(n.AuxUnsigned())
	}
	if c, found := po.constants[val]; found {
		po.values[n.ID] = c
		po.upushalias(n.ID, 0)
		return
	}

	// 为该常数创建新节点
	i := po.newnode(n)

	// 如果这是第一个常数，请将其作为新根，如
	// 我们无法记录现有连接，因此我们没有
	// 要将其添加到的特定DAG。请注意，我们希望所有
	// 常量都位于根#0中，因此请确保新的根
	// 位于那里。
	if len(po.constants) == 0 {
		idx := len(po.roots)
		po.roots = append(po.roots, i)
		po.roots[0], po.roots[idx] = po.roots[idx], po.roots[0]
		po.upush(undoNewRoot, i, 0)
		po.constants[val] = i
		po.upushconst(i, 0)
		return
	}

	// 在现有常数中查找下限和上限。也就是说，找一个比我们要加的更高的常数，和一个更高的常数。
	// 循环被复制以处理有符号和无符号比较，
	// 这取决于偏序集的配置方式。
	var lowerptr, higherptr uint32

	if po.flags&posetFlagUnsigned != 0 {
		var lower, higher uint64
		val1 := n.AuxUnsigned()
		for val2, ptr := range po.constants {
			val2 := uint64(val2)
			if val1 == val2 {
				panic("unreachable")
			}
			if val2 < val1 && (lowerptr == 0 || val2 > lower) {
				lower = val2
				lowerptr = ptr
			} else if val2 > val1 && (higherptr == 0 || val2 < higher) {
				higher = val2
				higherptr = ptr
			}
		}
	} else {
		var lower, higher int64
		val1 := n.AuxInt
		for val2, ptr := range po.constants {
			if val1 == val2 {
				panic("unreachable")
			}
			if val2 < val1 && (lowerptr == 0 || val2 > lower) {
				lower = val2
				lowerptr = ptr
			} else if val2 > val1 && (higherptr == 0 || val2 < higher) {
				higher = val2
				higherptr = ptr
			}
		}
	}

	if lowerptr == 0 && higherptr == 0 {
		// 这不应该发生，因为如果我们到这里，至少有一个
		// 其他常量必须存在。
		panic("no constant found")
	}

	// 创建新节点并将其连接到边界，以便
	// 更低<n<更高。根据偏序集中存在的其他常数，我们可以找到两个边界，或者只找到其中的一个
	// 边界。注意，我们总是把常数链接在一起，所以它们总是同一个DAG的一部分。
	switch {
	case lowerptr != 0 && higherptr != 0:
		// 两个边界都存在，记录下限<n<上限。
		po.addchild(lowerptr, i, true)
		po.addchild(i, higherptr, true)

	case lowerptr != 0:
		// 仅下限，记录下限<n.
		po.addchild(lowerptr, i, true)

	case higherptr != 0:
		// 仅上限。要记录n<更高，我们需要额外的根：
		// 
		// EXTRACT 
		// \
		// /root\
		// /n 
		// 
		// /\/
		// 更高的
		// 
		i2 := higherptr
		r2 := po.findroot(i2)
		if r2 != po.roots[0] { // 所有常量都应该在根目录中#0 
			panic("constant not in root #0")
		}
		extra := po.newnode(nil)
		po.changeroot(r2, extra)
		po.upush(undoChangeRoot, extra, newedge(r2, false))
		po.addchild(extra, r2, false)
		po.addchild(extra, i, false)
		po.addchild(i, i2, true)
	}

	po.constants[val] = i
	po.upushconst(i, 0)
}

// aliasnewnode记录一个节点n2（尚未在偏序集中）是主节点n1的别名
// 。
func (po *poset) aliasnewnode(n1, n2 *Value) {
	i1, i2 := po.values[n1.ID], po.values[n2.ID]
	if i1 == 0 || i2 != 0 {
		panic("aliasnewnode invalid arguments")
	}

	po.values[n2.ID] = i1
	po.upushalias(n2.ID, 0)
}

// aliasnodes记录所有节点I2都是单个主节点n1的别名。
// 别名节点负责重新排列DAG，更改i2s中节点的父/子
// 的引用，以便它们指向n1。
// 复杂性是O（n）（n是偏序集中的节点总数，而不仅仅是
// 被别名化的节点数）。
func (po *poset) aliasnodes(n1 *Value, i2s bitset) {
	i1 := po.values[n1.ID]
	if i1 == 0 {
		panic("aliasnode for non-existing node")
	}
	if i2s.Test(i1) {
		panic("aliasnode i2s contains n1 node")
	}

	// 遍历所有节点以调整i2s中节点的父/子节点
	for idx, n := range po.nodes {
		// 不要触摸i1本身，否则我们可以创建无用的自循环
		if uint32(idx) == i1 {
			continue
		}
		l, r := n.l, n.r

		// 将所有对i2s的引用重命名为i1 
		if i2s.Test(l.Target()) {
			po.setchl(uint32(idx), newedge(i1, l.Strict()))
			po.upush(undoSetChl, uint32(idx), l)
		}
		if i2s.Test(r.Target()) {
			po.setchr(uint32(idx), newedge(i1, r.Strict()))
			po.upush(undoSetChr, uint32(idx), r)
		}

		// 将i2s的所有子对象连接到i1（除非那些子对象
		// 也在i2s中，在这种情况下它将是无用的）
		if i2s.Test(uint32(idx)) {
			if l != 0 && !i2s.Test(l.Target()) {
				po.addchild(i1, l.Target(), l.Strict())
			}
			if r != 0 && !i2s.Test(r.Target()) {
				po.addchild(i1, r.Target(), r.Strict())
			}
			po.setchl(uint32(idx), 0)
			po.setchr(uint32(idx), 0)
			po.upush(undoSetChl, uint32(idx), l)
			po.upush(undoSetChr, uint32(idx), r)
		}
	}

	// 重新分配所有指向i2到i1的现有ID。
	// 这包括氮气。ID.
	for k, v := range po.values {
		if i2s.Test(v) {
			po.values[k] = i1
			po.upushalias(k, v)
		}
	}

	// 如果其中一个别名节点是常数，则确保
	// po。常量更新为指向主节点。
	for val, idx := range po.constants {
		if i2s.Test(idx) {
			po.constants[val] = i1
			po.upushconst(i1, idx)
		}
	}
}

func (po *poset) isroot(r uint32) bool {
	for i := range po.roots {
		if po.roots[i] == r {
			return true
		}
	}
	return false
}

func (po *poset) changeroot(oldr, newr uint32) {
	for i := range po.roots {
		if po.roots[i] == oldr {
			po.roots[i] = newr
			return
		}
	}
	panic("changeroot on non-root")
}

func (po *poset) removeroot(r uint32) {
	for i := range po.roots {
		if po.roots[i] == r {
			po.roots = append(po.roots[:i], po.roots[i+1:]...)
			return
		}
	}
	panic("removeroot on non-root")
}

// dfs在根为r的DAG中执行深度优先搜索。
// f是为每个节点调用的访问函数；如果返回true，则
// 搜索中止，返回true。根节点也是
// 已访问。
// 如果严格，忽略路径上的边，直到找到至少一条
// 严格边。例如，对于链a<=B<=C<D<=E<F，
// 严格步行访问D，E，F。
// 如果访问结束，则返回false。
func (po *poset) dfs(r uint32, strict bool, f func(i uint32) bool) bool {
	closed := newBitset(int(po.lastidx + 1))
	open := make([]uint32, 1, 64)
	open[0] = r

	if strict {
		// 做第一个DFS；当我们找到一条严格的
		// 边时，走所有路径并停止，建立一个“下一个”节点列表，这些节点可以通过严格的
		// 边访问。这将是真正DFS的引导打开列表。
		next := make([]uint32, 0, 64)

		for len(open) > 0 {
			i := open[len(open)-1]
			open = open[:len(open)-1]

			// 不要访问同一个节点两次。请注意，非严格路径中的所有节点
			// 仍至少被访问一次，因此
			// 非严格路径永远不能掩盖到同一节点的严格路径。
			if !closed.Test(i) {
				closed.Set(i)

				l, r := po.children(i)
				if l != 0 {
					if l.Strict() {
						next = append(next, l.Target())
					} else {
						open = append(open, l.Target())
					}
				}
				if r != 0 {
					if r.Strict() {
						next = append(next, r.Target())
					} else {
						open = append(open, r.Target())
					}
				}
			}
		}
		open = next
		closed.Reset()
	}

	for len(open) > 0 {
		i := open[len(open)-1]
		open = open[:len(open)-1]

		if !closed.Test(i) {
			if f(i) {
				return true
			}
			closed.Set(i)
			l, r := po.children(i)
			if l != 0 {
				open = append(open, l.Target())
			}
			if r != 0 {
				open = append(open, r.Target())
			}
		}
	}
	return false
}

// 如果存在从i1到i2的路径，则返回true。
// If strict==true：如果函数返回true，则i1<i2。
// If strict==false：如果函数返回true，则i1<=i2。
// 如果函数返回false，则不知道任何关系。
func (po *poset) reaches(i1, i2 uint32, strict bool) bool {
	return po.dfs(i1, strict, func(n uint32) bool {
		return n == i2
	})
}

// findroot找到i的根，即DAG包含i的根。
// 返回根；如果我本身是根，它就会被返回。
// 如果我不在任何DAG，请惊慌。
func (po *poset) findroot(i uint32) uint32 {
	// TODO（rasky）：如果需要，可以通过
	// 为每个根存储一个位集，将其用作该根下存在的节点的迷你bloom过滤器
	// 来加快搜索速度。
	for _, r := range po.roots {
		if po.reaches(r, i, false) {
			return r
		}
	}
	panic("findroot didn't find any root")
}

// mergeroot通过创建新的额外根将两个DAG合并为一个DAG 
func (po *poset) mergeroot(r1, r2 uint32) uint32 {
	// root#0是特殊的，因为它包含所有常量。由于mergeroot 
	// 将r2作为根丢弃并保留r1，请确保r2不是根#0，否则常量将移动到另一个根。
	if r2 == po.roots[0] {
		r1, r2 = r2, r1
	}
	r := po.newnode(nil)
	po.setchl(r, newedge(r1, false))
	po.setchr(r, newedge(r2, false))
	po.changeroot(r1, r)
	po.removeroot(r2)
	po.upush(undoMergeRoot, r, 0)
	return r
}

// 折叠路径将n1和n2标记为相等，并将n1和n2之间所有路径上的所有节点折叠为相等。如果strict edge为
// found，则函数不会修改DAG并返回false。
// 复杂性为O（n）。
func (po *poset) collapsepath(n1, n2 *Value) bool {
	i1, i2 := po.values[n1.ID], po.values[n2.ID]
	if po.reaches(i1, i2, true) {
		return false
	}

	// 查找从i1到i2的所有路径
	paths := po.findpaths(i1, i2)
	// 将所有路径中的所有节点标记为n1的别名
	// （不包括n1本身）
	paths.Clear(i1)
	po.aliasnodes(n1, paths)
	return true
}

// findpaths是一个递归函数，它计算从cur到dst的所有路径
// 并将它们作为位集返回（如果
// 某个节点位于从cur到dst的至少一条路径上，则在位集中设置该节点的索引）。
// 我们从cur进行DFS（在任何时候到达dst时停止深入），
// 并将任何具有子节点的节点标记为路径的一部分，该子节点已经是路径的一部分（或是dst本身）。
func (po *poset) findpaths(cur, dst uint32) bitset {
	seen := newBitset(int(po.lastidx + 1))
	path := newBitset(int(po.lastidx + 1))
	path.Set(dst)
	po.findpaths1(cur, dst, seen, path)
	return path
}

func (po *poset) findpaths1(cur, dst uint32, seen bitset, path bitset) {
	if cur == dst {
		return
	}
	seen.Set(cur)
	l, r := po.chl(cur), po.chr(cur)
	if !seen.Test(l) {
		po.findpaths1(l, dst, seen, path)
	}
	if !seen.Test(r) {
		po.findpaths1(r, dst, seen, path)
	}
	if path.Test(l) || path.Test(r) {
		path.Set(cur)
	}
}

// 检查是否记录了i1=i2 
func (po *poset) isnoneq(i1, i2 uint32) bool {
	if i1 == i2 {
		return false
	}
	if i1 < i2 {
		i1, i2 = i2, i1
	}

	// 检查我们在
	if bs, ok := po.noneq[i1]; ok && bs.Test(i2) {
		return true
	}
	return false
}

// 之前是否记录了一个不相等的关系=i2 
func (po *poset) setnoneq(n1, n2 *Value) {
	i1, f1 := po.lookup(n1)
	i2, f2 := po.lookup(n2)

	// 如果偏序集中不存在任何节点，请分配它们。由于
	// 我们不知道它们之间的任何关系（部分顺序），它们必须成为独立的根。
	if !f1 {
		i1 = po.newnode(n1)
		po.roots = append(po.roots, i1)
		po.upush(undoNewRoot, i1, 0)
	}
	if !f2 {
		i2 = po.newnode(n2)
		po.roots = append(po.roots, i2)
		po.upush(undoNewRoot, i2, 0)
	}

	if i1 == i2 {
		panic("setnoneq on same node")
	}
	if i1 < i2 {
		i1, i2 = i2, i1
	}
	bs := po.noneq[i1]
	if bs == nil {
		// 考虑到我们使用更高的索引作为键来记录非等式关系，比特大小永远不会改变。ABCFDG
		bs = newBitset(int(i1))
		po.noneq[i1] = bs
	} else if bs.Test(i2) {
		// 已记录
		return
	}
	bs.Set(i2)
	po.upushneq(i1, i2)
}

// CheckIntegrity验证偏序集的内部完整性。用于调试目的。
func (po *poset) CheckIntegrity() {
	// 记录哪个索引是常量
	constants := newBitset(int(po.lastidx + 1))
	for _, c := range po.constants {
		constants.Set(c)
	}

	// 验证每个节点出现在单个DAG中，并且
	// 所有常量都在第一个DAG中
	seen := newBitset(int(po.lastidx + 1))
	for ridx, r := range po.roots {
		if r == 0 {
			panic("empty root")
		}

		po.dfs(r, false, func(i uint32) bool {
			if seen.Test(i) {
				panic("duplicate node")
			}
			seen.Set(i)
			if constants.Test(i) {
				if ridx != 0 {
					panic("constants not in the first DAG")
				}
			}
			return false
		})
	}

	// 验证值是否包含最小集
	for id, idx := range po.values {
		if !seen.Test(idx) {
			panic(fmt.Errorf("spurious value [%d]=%d", id, idx))
		}
	}

	// 验证只有现有节点具有非零子节点
	for i, n := range po.nodes {
		if n.l|n.r != 0 {
			if !seen.Test(uint32(i)) {
				panic(fmt.Errorf("children of unknown node %d->%v", i, n))
			}
			if n.l.Target() == uint32(i) || n.r.Target() == uint32(i) {
				panic(fmt.Errorf("self-loop on node %d", i))
			}
		}
	}
}

// CheckEmpty检查偏序集是否完全为空。
// 它可以用于调试目的，因为偏序集应该在通过Undo完全回滚后为空。
func (po *poset) CheckEmpty() error {
	if len(po.nodes) != 1 {
		return fmt.Errorf("non-empty nodes list: %v", po.nodes)
	}
	if len(po.values) != 0 {
		return fmt.Errorf("non-empty value map: %v", po.values)
	}
	if len(po.roots) != 0 {
		return fmt.Errorf("non-empty root list: %v", po.roots)
	}
	if len(po.constants) != 0 {
		return fmt.Errorf("non-empty constants: %v", po.constants)
	}
	if len(po.undo) != 0 {
		return fmt.Errorf("non-empty undo list: %v", po.undo)
	}
	if po.lastidx != 0 {
		return fmt.Errorf("lastidx index is not zero: %v", po.lastidx)
	}
	for _, bs := range po.noneq {
		for _, x := range bs {
			if x != 0 {
				return fmt.Errorf("non-empty noneq map")
			}
		}
	}
	return nil
}

// DotDump将图形格式的偏序集转储到具有指定标题的文件fn中。
func (po *poset) DotDump(fn string, title string) error {
	f, err := os.Create(fn)
	if err != nil {
		return err
	}
	defer f.Close()

	// 创建反向索引映射（考虑别名）
	names := make(map[uint32]string)
	for id, i := range po.values {
		s := names[i]
		if s == "" {
			s = fmt.Sprintf("v%d", id)
		} else {
			s += fmt.Sprintf(", v%d", id)
		}
		names[i] = s
	}

	// 创建反向常量映射
	consts := make(map[uint32]int64)
	for val, idx := range po.constants {
		consts[idx] = val
	}

	fmt.Fprintf(f, "digraph poset {\n")
	fmt.Fprintf(f, "\tedge [ fontsize=10 ]\n")
	for ridx, r := range po.roots {
		fmt.Fprintf(f, "\tsubgraph root%d {\n", ridx)
		po.dfs(r, false, func(i uint32) bool {
			if val, ok := consts[i]; ok {
				// 常量
				var vals string
				if po.flags&posetFlagUnsigned != 0 {
					vals = fmt.Sprint(uint64(val))
				} else {
					vals = fmt.Sprint(int64(val))
				}
				fmt.Fprintf(f, "\t\tnode%d [shape=box style=filled fillcolor=cadetblue1 label=<%s <font point-size=\"6\">%s [%d]</font>>]\n",
					i, vals, names[i], i)
			} else {
				// 正常SSA值
				fmt.Fprintf(f, "\t\tnode%d [label=<%s <font point-size=\"6\">[%d]</font>>]\n", i, names[i], i)
			}
			chl, chr := po.children(i)
			for _, ch := range []posetEdge{chl, chr} {
				if ch != 0 {
					if ch.Strict() {
						fmt.Fprintf(f, "\t\tnode%d -> node%d [label=\" <\" color=\"red\"]\n", i, ch.Target())
					} else {
						fmt.Fprintf(f, "\t\tnode%d -> node%d [label=\" <=\" color=\"green\"]\n", i, ch.Target())
					}
				}
			}
			return false
		})
		fmt.Fprintf(f, "\t}\n")
	}
	fmt.Fprintf(f, "\tlabelloc=\"t\"\n")
	fmt.Fprintf(f, "\tlabeldistance=\"3.0\"\n")
	fmt.Fprintf(f, "\tlabel=%q\n", title)
	fmt.Fprintf(f, "}\n")
	return nil
}

// 有序报告n1是否小于n2。当它是
// 确定n1<n2为假时，或者如果
// 没有足够的信息来说明，则返回false。
// 复杂性为O（n）。
func (po *poset) Ordered(n1, n2 *Value) bool {
	if debugPoset {
		defer po.CheckIntegrity()
	}
	if n1.ID == n2.ID {
		panic("should not call Ordered with n1==n2")
	}

	i1, f1 := po.lookup(n1)
	i2, f2 := po.lookup(n2)
	if !f1 || !f2 {
		return false
	}

	return i1 != i2 && po.reaches(i1, i2, true)
}

// OrderedRequal报告n1是否小于等于n2。当它是
// 确定n1<=n2为假，或者如果
// 没有足够的信息来说明，则返回false。
// 复杂性为O（n）。
func (po *poset) OrderedOrEqual(n1, n2 *Value) bool {
	if debugPoset {
		defer po.CheckIntegrity()
	}
	if n1.ID == n2.ID {
		panic("should not call Ordered with n1==n2")
	}

	i1, f1 := po.lookup(n1)
	i2, f2 := po.lookup(n2)
	if !f1 || !f2 {
		return false
	}

	return i1 == i2 || po.reaches(i1, i2, false)
}

// Equal报告n1==n2。当它是
// 确定n1==n2为假时，或者如果没有足够的信息
// 来说明，则返回false。
// 复杂性为O（1）。
func (po *poset) Equal(n1, n2 *Value) bool {
	if debugPoset {
		defer po.CheckIntegrity()
	}
	if n1.ID == n2.ID {
		panic("should not call Equal with n1==n2")
	}

	i1, f1 := po.lookup(n1)
	i2, f2 := po.lookup(n2)
	return f1 && f2 && i1 == i2
}

// 非相等报告是否为n1=氮气。当它是
// /确定n1时，它返回false=n2为假，或者
// 没有足够的信息来说明。
// 复杂性是O（n）（因为它在内部调用Ordered，以查看我们
// 是否可以从n1<n2或n2<n1中推断n1！=n2）。
func (po *poset) NonEqual(n1, n2 *Value) bool {
	if debugPoset {
		defer po.CheckIntegrity()
	}
	if n1.ID == n2.ID {
		panic("should not call NonEqual with n1==n2")
	}

	// 如果我们以前从未见过节点，我们就不会有记录的不相等。
	i1, f1 := po.lookup(n1)
	i2, f2 := po.lookup(n2)
	if !f1 || !f2 {
		return false
	}

	// 检查我们是否记录了不等式
	if po.isnoneq(i1, i2) {
		return true
	}

	// 检查n1<n2或n2<n1，在这种情况下我们可以推断n1=n2 
	if po.Ordered(n1, n2) || po.Ordered(n2, n1) {
		return true
	}

	return false
}

// setOrder记录n1<n2或n1<=n2（取决于严格要求）。返回false 
// 如果这是矛盾的话。
// 实现SetOrder（）和setOrdereQual（）
func (po *poset) setOrder(n1, n2 *Value, strict bool) bool {
	i1, f1 := po.lookup(n1)
	i2, f2 := po.lookup(n2)

	switch {
	case !f1 && !f2:
		// n1和n2都不在偏序集中，因此它们与现有节点没有任何关联。
		// 创建一个新的DAG来记录关系。
		i1, i2 = po.newnode(n1), po.newnode(n2)
		po.roots = append(po.roots, i1)
		po.upush(undoNewRoot, i1, 0)
		po.addchild(i1, i2, strict)

	case f1 && !f2:
		// n1在其中一个DAG中，而n2不在。添加n2作为n1的子项
		// 。
		i2 = po.newnode(n2)
		po.addchild(i1, i2, strict)

	case !f1 && f2:
		// n1不在任何DAG中，但n2在任何DAG中。如果n2是根，我们可以把
		// n1放在根的位置；否则，我们需要创建一个新的
		// 额外的根来记录关系。
		i1 = po.newnode(n1)

		if po.isroot(i2) {
			po.changeroot(i2, i1)
			po.upush(undoChangeRoot, i1, newedge(i2, strict))
			po.addchild(i1, i2, strict)
			return true
		}

		// 搜索i2的根；这需要对所有
		// DAGs 
		r := po.findroot(i2)

		// Re parent进行O（n）搜索，如下所示：
		// 
		// extra 
		// r/\
		// ==r i1 
		// i2\/
		// i2 
		// 
		extra := po.newnode(nil)
		po.changeroot(r, extra)
		po.upush(undoChangeRoot, extra, newedge(r, false))
		po.addchild(extra, r, false)
		po.addchild(extra, i1, false)
		po.addchild(i1, i2, strict)

	case f1 && f2:
		// （也就是说，如果n1==n2，我们不能设置n1<n2）。
		if i1 == i2 {
			return !strict
		}

		// 如果我们试图记录n1<=n2，但我们了解到n1=n2，
		// 记录n1<n2，因为它提供了更多信息。
		if !strict && po.isnoneq(i1, i2) {
			strict = true
		}

		// n1和n2都在偏序集中。这是算法
		// /的复杂部分，因为我们需要找到许多不同的情况和DAG形状。这是我们需要处理的所有案件的表格：

		if po.reaches(i1, i2, false) {
			// 
			// DAG新行动
			// ---------------------------------------
			// 1:n1<=X<=n2 124N1<=n2 |什么都不做
			// /\2:n1<=X<=n2 |添加严格边缘（N1<N2）
			// /#3:N1<X<N2 | N1<=N2 |什么都不做（我们已经知道更多）
			// /#4:N1<X<N2 | N1<N2 |什么都不做

			// /检查我们是否在案例中#2 
			if strict && !po.reaches(i1, i2, true) {
				po.addchild(i1, i2, true)
				return true
			}

			// /#案例1，#3 o#4:无事可做
			return true
		}

		// 检查n2是否以某种方式到达n1 
		if po.reaches(i2, i1, false) {
			// 这是我们需要处理的所有情况的表格：
			// 
			// DAG新操作
			// /---------------------------------------
			// /\5:n2<=X<=n1<=n1<=n2<=n2 |崩溃路径（了解n1=X=n2）矛盾矛盾矛盾矛盾矛盾矛盾矛盾矛盾矛盾。尝试让路径崩溃，如果它意识到我们在案例7中，那么它将失败。

			if strict {
				return false
			}

			return po.collapsepath(n2, n1)
		}

		// 我们不知道n1和n2之间存在任何关系。他们可以
		// 是否属于同一个DAG。
		// 找到它们的根，检查它们是否在同一个DAG中。
		r1, r2 := po.findroot(i1), po.findroot(i2)
		if r1 != r2 {
			// 我们需要合并两个DAG来记录节点之间的关系
			po.mergeroot(r1, r2)
		}

		// 连接n1和n2 
		po.addchild(i1, i2, strict)
	}

	return true
}

// SetOrder记录n1<n2。如果这是一个矛盾，则返回false 
// 如果之前从未见过n2，则复杂性为O（1），否则为O（n）。
func (po *poset) SetOrder(n1, n2 *Value) bool {
	if debugPoset {
		defer po.CheckIntegrity()
	}
	if n1.ID == n2.ID {
		panic("should not call SetOrder with n1==n2")
	}
	return po.setOrder(n1, n2, true)
}

// setOrdereQual记录n1<=n2。如果这是一个矛盾，则返回false 
// 如果之前从未见过n2，则复杂性为O（1），否则为O（n）。
func (po *poset) SetOrderOrEqual(n1, n2 *Value) bool {
	if debugPoset {
		defer po.CheckIntegrity()
	}
	if n1.ID == n2.ID {
		panic("should not call SetOrder with n1==n2")
	}
	return po.setOrder(n1, n2, false)
}

// SetEqual记录n1==n2。如果这是矛盾
// /（即，如果已经记录到n1<n2或n2<n1），则返回false。
// 如果之前从未见过n2，则复杂度为O（1），否则为O（n）。
func (po *poset) SetEqual(n1, n2 *Value) bool {
	if debugPoset {
		defer po.CheckIntegrity()
	}
	if n1.ID == n2.ID {
		panic("should not call Add with n1==n2")
	}

	i1, f1 := po.lookup(n1)
	i2, f2 := po.lookup(n2)

	switch {
	case !f1 && !f2:
		i1 = po.newnode(n1)
		po.roots = append(po.roots, i1)
		po.upush(undoNewRoot, i1, 0)
		po.aliasnewnode(n1, n2)
	case f1 && !f2:
		po.aliasnewnode(n1, n2)
	case !f1 && f2:
		po.aliasnewnode(n2, n1)
	case f1 && f2:
		if i1 == i2 {
			// 已经化名，忽略
			return true
		}

		// 如果我们记录了n1=这是一个矛盾。
		if po.isnoneq(i1, i2) {
			return false
		}

		// 如果我们已经知道n1<=n2，我们可以折叠到
		// 记录n1==n2（反之亦然）。
		if po.reaches(i1, i2, false) {
			return po.collapsepath(n1, n2)
		}
		if po.reaches(i2, i1, false) {
			return po.collapsepath(n2, n1)
		}

		r1 := po.findroot(i1)
		r2 := po.findroot(i2)
		if r1 != r2 {
			// 合并两个DAG，以便记录节点之间的关系
			po.mergeroot(r1, r2)
		}

		// 将n2设置为n1的别名。这也将更新所有对n2的引用
		// 以成为对n1的引用
		i2s := newBitset(int(po.lastidx) + 1)
		i2s.Set(i2)
		po.aliasnodes(n1, i2s)
	}
	return true
}

// 设置n1=氮气。如果这是一个矛盾
// /（即，如果已经记录n1==n2），则返回false。
// 复杂性为O（n）。
func (po *poset) SetNonEqual(n1, n2 *Value) bool {
	if debugPoset {
		defer po.CheckIntegrity()
	}
	if n1.ID == n2.ID {
		panic("should not call SetNonEqual with n1==n2")
	}

	// 检查节点是否已经在偏序集中
	i1, f1 := po.lookup(n1)
	i2, f2 := po.lookup(n2)

	// 如果其中一个节点不存在，我们只记录新的关系
	// 并退出。
	if !f1 || !f2 {
		po.setnoneq(n1, n2)
		return true
	}

	// 看看我们是否已经知道了这一点，在这种情况下没有什么可做的。
	if po.isnoneq(i1, i2) {
		return true
	}

	// 检查我们是否与现有的平等关系相矛盾
	if po.Equal(n1, n2) {
		return false
	}

	// 记录不平等
	po.setnoneq(n1, n2)

	// 如果我们知道i1<=i2，但不是i1<i2，那么当我们
	// 现在知道它们是不平等的。对i2<=i1执行同样的操作。
	// 仅当两个节点都已在DAG中时执行此检查，否则不能存在现有关系。
	if po.reaches(i1, i2, false) && !po.reaches(i1, i2, true) {
		po.addchild(i1, i2, true)
	}
	if po.reaches(i2, i1, false) && !po.reaches(i2, i1, true) {
		po.addchild(i2, i1, true)
	}

	return true
}

// 检查点保存DAG的当前状态，以便以后可以撤消此状态。
// 复杂性为O（1）。
func (po *poset) Checkpoint() {
	po.undo = append(po.undo, posetUndo{typ: undoCheckpoint})
}

// 撤消将偏序集的状态恢复到上一个检查点。
// 复杂性取决于自上一个检查点以来执行的操作类型
// ；每个Set*操作都会创建一个undo 
// 过程，该过程必须以O（n）的最坏情况复杂度进行恢复。
func (po *poset) Undo() {
	if len(po.undo) == 0 {
		panic("empty undo stack")
	}
	if debugPoset {
		defer po.CheckIntegrity()
	}

	for len(po.undo) > 0 {
		pass := po.undo[len(po.undo)-1]
		po.undo = po.undo[:len(po.undo)-1]

		switch pass.typ {
		case undoCheckpoint:
			return

		case undoSetChl:
			po.setchl(pass.idx, pass.edge)

		case undoSetChr:
			po.setchr(pass.idx, pass.edge)

		case undoNonEqual:
			po.noneq[uint32(pass.ID)].Clear(pass.idx)

		case undoNewNode:
			if pass.idx != po.lastidx {
				panic("invalid newnode index")
			}
			if pass.ID != 0 {
				if po.values[pass.ID] != pass.idx {
					panic("invalid newnode undo pass")
				}
				delete(po.values, pass.ID)
			}
			po.setchl(pass.idx, 0)
			po.setchr(pass.idx, 0)
			po.nodes = po.nodes[:pass.idx]
			po.lastidx--

		case undoNewConstant:
			// 修复：删除此O（n）循环
			var val int64
			var i uint32
			for val, i = range po.constants {
				if i == pass.idx {
					break
				}
			}
			if i != pass.idx {
				panic("constant not found in undo pass")
			}
			if pass.ID == 0 {
				delete(po.constants, val)
			} else {
				// 将以前的索引恢复为常量节点
				// （也恢复正确边界上的不变量）
				oldidx := uint32(pass.ID)
				po.constants[val] = oldidx
			}

		case undoAliasNode:
			ID, prev := pass.ID, pass.idx
			cur := po.values[ID]
			if prev == 0 {
				// 作为别名出生，作为别名死亡
				delete(po.values, ID)
			} else {
				if cur == prev {
					panic("invalid aliasnode undo pass")
				}
				// 将其返回以前的值
				po.values[ID] = prev
			}

		case undoNewRoot:
			i := pass.idx
			l, r := po.children(i)
			if l|r != 0 {
				panic("non-empty root in undo newroot")
			}
			po.removeroot(i)

		case undoChangeRoot:
			i := pass.idx
			l, r := po.children(i)
			if l|r != 0 {
				panic("non-empty root in undo changeroot")
			}
			po.changeroot(i, pass.edge.Target())

		case undoMergeRoot:
			i := pass.idx
			l, r := po.children(i)
			po.changeroot(i, l.Target())
			po.roots = append(po.roots, r.Target())

		default:
			panic(pass.typ)
		}
	}

	if debugPoset && po.CheckEmpty() != nil {
		panic("poset not empty at the end of undo")
	}
}
